package Sequence;

public class Test0684 {
}

class Solution0684_01 {
    int[] records;
    public int[] findRedundantConnection(int[][] edges) {
        init(edges.length+1);

        for (int[] edge : edges) {
            if (!same(edge[0],edge[1])) {
                join(edge[0],edge[1]);
            }else {
                return edge;
            }
        }

        return null;
    }

    public void init(int length){
        records = new int[length];
        for (int i = 0; i < length; i++) {
            records[i] =i;
        }
    }

    public int find(int u) {
        if (records[u] == u) return u;
        return records[u] = find(records[u]);
    }

    public boolean same(int x, int y){
        return find(x) == find(y);
    }

    public void join(int x,int y){
        int x1 = find(x);
        int y1 = find(y);

        if (x1 != y1)
            records[x1] = y1;
    }
}
